//给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 
//
// 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 
//
// 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 
//
// 示例： 
//
// 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
//输出：7 -> 0 -> 8
//原因：342 + 465 = 807
// 
// Related Topics 链表 数学 
// 👍 4714 👎 0

package leetcode.editor.cn;

//Java：两数相加
public class P2AddTwoNumbers {

//leetcode submit region begin(Prohibit modification and deletion)
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 思路：先不管一位的限制都加起来，然后再优化加起来的链表
     * 例如:9876 + 54,第一个先按位加起来，得到  9 8 12 10，然后再遍历%10，需要进位的，加一后再%10  得到    9 9 3 0
     */
    class Solution {
        private ListNode addVal(ListNode node, int val) {
            ListNode oldFirst = node;
            node = new ListNode(val);
            node.next = oldFirst;
            return node;
        }


        private ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode sumNode = sum(l1, l2);
            carry(null, sumNode, false);
            return sumNode;
        }

        // 两个node直接相加
        private ListNode sum(ListNode l1, ListNode l2) {
            if (l1 == null && l2 == null) {
                return null;
            }
            ListNode sumNode = new ListNode(0);
            int sum;
            if (l1 == null) {
                sum = l2.val;
                sumNode.next = sum(null, l2.next);
            } else if (l2 == null) {
                sum = l1.val;
                sumNode.next = sum(l1.next, null);
            } else {
                sum = l1.val + l2.val;
                sumNode.next = sum(l1.next, l2.next);
            }
            sumNode.val = sum;
            return sumNode;
        }

        // 合计的node 大于10的进一      ,flag 是否进一位  只能是进一，就算是  999+999=18,18,18 也是进一位
        private void carry(ListNode parent, ListNode node, boolean flag) {
            // 空结点，不用进一
            if (node == null && !flag) {
                return;
            }
            // 空结点，但是得进一
            if (node == null) {
                parent.next = new ListNode(1);
                return;
            }
            int a = flag ? node.val + 1 : node.val;
            flag = false;
            if (a >= 10) {
                a = a % 10;
                flag = true;
            }
            node.val = a;
            carry(node, node.next, flag);
        }
    }


//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P2AddTwoNumbers().new Solution();
        // TO TEST

        ListNode node = new ListNode(9);
        node = solution.addVal(node, 5);
        node = solution.addVal(node, 0);

        ListNode node2 = new ListNode(5);
        node2 = solution.addVal(node2, 0);

        solution.addTwoNumbers(node, node2);
    }

}